#include "seq-list.cpp"

/***
 * 简单选择排序
 * 基本思路: 每趟从待排序的记录中选出关键字最小的记录, 顺序放在已排序记录序列末尾
 * 时间复杂度: 平均 O(n^2) 最优O(n) 最坏O(n^2)
 * 空间复杂度: O(1)
 * 稳定性: 不稳定
 * */

void sort(SqList &L)
{
    for (int i = 0; i < L.length; i++)
    {
        int index = i; // 未排序序列中的最小值
        for (int j = i; j < L.length; j++)
        {
            if (L.data[j] < L.data[i])
                index = j;
        }
        // 将当前i 与最小值交换
        swap(L, index, i);
        // 输出过程
        printf("第 %d 趟:",i+1);
        printList(L);
    }
}

int main()
{
    SqList L;
    int data[6] = {6, 5, 3, 2, 7, 1};
    L.data = data;
    L.length = 6;
    printList(L);
    sort(L);
    printList(L);
    return 0;
}